package ads1ss13.pa;

/**
 * Sorter Klasse in der die Methode {@link #quicksort(DoublyLinkedList, int)}
 * implementiert werden soll.
 * 
 * <p>
 * In dieser Klasse m&uuml;ssen Sie Ihren Code einf&uuml;gen und die Method
 * {@link #quicksort(DoublyLinkedList, int)} implementieren.
 * </p>
 * 
 * <p>
 * Sie k&ouml;nnen beliebige neue Variablen und Methoden in dieser Klasse
 * hinzuf&uuml;gen.
 * </p>
 */

public class Sorter {

	/**
	 * Quicksort Implementierung
	 * 
	 * @param in
	 *            Unsortierte Eingabefolge
	 * @param numOfElements
	 *            Gr&ouml;&szlig;e der Eingabefolge
	 * @return Sortiterte Eingabefolge
	 */
	public DoublyLinkedList quicksort(DoublyLinkedList in, int numOfElements) {
		ListElement l = in.first;
		ListElement r = in.first.prev;

		quicksort_(in, true, l, r);
		return in;
	}

	private void quicksort_(DoublyLinkedList list, boolean start,
			ListElement l, ListElement r) {
		if (l == r)
			return;

		if (l.prev == r && !start) {
			return;
		}

		ListElement pivot = r;
		ListElement[] lr = new ListElement[2];
		lr[0] = l;
		lr[1] = r.prev;

		partition(list, lr, pivot);

		quicksort_(list, false, lr[0], pivot.prev);
		quicksort_(list, false, pivot.next, lr[1]);
	}

	private void partition(DoublyLinkedList list, ListElement[] lr,
			ListElement p) {
		ListElement l = lr[0];
		ListElement r = lr[1];

		boolean lChanged = false;

		while (l.prev != r) {
			while (l.getKey() <= p.getKey() && l.prev != r) {
				lChanged = true;
				l = l.next;
			}

			while (r.getKey() > p.getKey() && l.prev != r)
				r = r.prev;

			if (l.prev != r) {
				swap(l, r);
				ListElement tmp = l;
				l = r;
				r = tmp;

				if (!lChanged) {
					if (list.first == lr[0])
						list.first = l;
					lr[0] = l;
					lChanged = true;
				}
			}
		}

		if (l.getKey() > p.getKey()) {
			if (!lChanged) {
				if (list.first == lr[0])
					list.first = p;
				lr[0] = p;
			}
			swap(l, p);
			lr[1] = l;
		} else {
			lr[1] = p;
		}
	}

	private void swap(ListElement l, ListElement r) {
		ListElement lPrev = l.prev;
		ListElement lNext = l.next;
		ListElement rPrev = r.prev;

		if (r.prev == l) {
			l.prev = r;
			l.next = r.next;
			r.next.prev = l;

			r.next = l;
			lPrev.next = r;
			r.prev = lPrev;

		} else if (r.next == l) {
			r.next = l.next;
			l.next.prev = r;
			r.prev = l;

			l.next = r;
			rPrev.next = l;
			l.prev = rPrev;
		} else {
			l.prev = r.prev;
			r.prev.next = l;
			l.next = r.next;
			r.next.prev = l;

			r.next = lNext;
			lNext.prev = r;
			lPrev.next = r;
			r.prev = lPrev;
		}
	}

	// public static void main(String[] args) {
	// Random r = new Random();
	// DoublyLinkedList list = new DoublyLinkedList(new ListElement(10001));
	//
	// int counter = 0;
	//
	// while (counter < 10) {
	// list.first.prev.next = new ListElement(1000 - counter);
	// list.first.prev.next.prev = list.first.prev;
	// list.first.prev.next.next = list.first;
	// list.first.prev = list.first.prev.next;
	// counter++;
	// }
	//
	// Sorter sorter = new Sorter();
	// sorter.quicksort(list, 0);
	// System.out.println("finished");
	// printList(list);
	// }

	public static void printList(DoublyLinkedList list) {
		ListElement tmp = list.first;

		do {
			System.out.print(tmp.getKey() + ",");
			tmp = tmp.next;
		} while (list.first != tmp);
		System.out.println();
	}
}
